class Solution {
public:
    int memo[201][201];

    int getMoneyAmount(int n) {
        return dfs(1, n);
    }

    int dfs(int i, int j)
    {
        if (i >= j) return 0;

        if (memo[i][j] != 0)
            return memo[i][j];

        int ret = INT_MAX;
        for (int k = i; k <= j; k++)
        {
            int left = dfs(i, k - 1);
            int right = dfs(k + 1, j);
            ret = min(ret, k + max(left, right));
        }

        memo[i][j] = ret;
        return ret;
    }
};